package top.minuy.structure.graph.path.bfs;

import top.minuy.structure.graph.representations.table.Graph;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 单源路径，广度优先遍历
 *
 * @author Minuy
 * @time 0:26
 * @date 2021/11/20
 */
public class SingleSourcePath {

    private Graph g;
    private boolean[] isVisited;

    private int[] pre;
    private int s;

    public SingleSourcePath(Graph g, int s) {
        this.g = g;
        this.s = s;

        isVisited = new boolean[g.V()];

        pre = new int[g.V()];
        for (int i=0;i<pre.length;i++){
            pre[i] = -1;
        }

        bfs(s);
    }

    private void bfs(int v) {
        // int parent = v;
        List<Integer> queue = new ArrayList<>();
        queue.add(v); // 根顶点入队
        isVisited[v] = true; // 入队的时候设置为true
        pre[v] = v; // 设置父节点也应该是在入队的时候
        // System.out.println("根顶点入队："+v);
        // System.out.println("==============");
        while (!queue.isEmpty()) {
            // 第一个元素出队
            v = queue.remove(0);
            // System.out.println("第一个元素出队并访问："+v);

            // 访问
            // order.add(v);

            for (int w : g.adj(v)) {
                if (!isVisited[w]) {  // 如果没被访问过
                    queue.add(w);  // 入队
                    // System.out.println("子顶点入队："+w);
                    isVisited[w] = true; // 入队的时候设置为true

                    pre[w] = v;// 设置父节点也应该是在入队的时候
                }
            }
        }
    }

    /**
     * 看两点是否联通
     *
     * @param t 目标点
     * @return boolean 源点s与目标点t是否联通
     * @author Minuy
     * @date 2021/11/20 0:31
     */
    public boolean isConnectedTo(int t) {
        g.validateVertex(t);
        return isVisited[t];
    }

    /**
     * 返回一个从源点s到目标点t的路径
     *
     * @param t 目标顶点t
     * @return Iterable<Integer> 路径列表
     * @author Minuy
     * @date 2021/11/20 0:36
     */
    public Iterable<Integer> path(int t) {
        ArrayList<Integer> p = new ArrayList<>();
        if (!isConnectedTo(t)) {
            return p;
        }

        int cur = t;
        while (cur != s) {
            p.add(cur);
            cur = pre[cur]; // 找自己的父顶点
        }
        p.add(s);

        Collections.reverse(p);
        return p;
    }

}
